CS-04 : DATA STRUCTURE THROUGH 'C' & PASCAL  DEC 1996

NOTE: Question 1 is compulsory. Attempt any three from the rest.  Algorithms should be written near to C or Pascal language statements.
 

1.	(a).	The order of nodes of a Binary tree in preorder and inorder traversal are as under:
		Preorder:  A  B  D  G  H  C  E  F  I  K  J Inorder :   B  G  H  D  A  E  C  I  K  F  J
		Draw the corresponding Binary tree.
	(b).	A recursive function f is shown below.  What is the value of f(5) ?
		int f(int x)                  {                          if (x < 2)                                   return (1);                           else                                  return f (x - 1) + f (x - 2)
	(c).	Given array A (50 : 100, 50  :  75).  What is the starting location of A(62, 56) ?
	(e).	Write the following expression into postfix  notation.
	(f).	The following keys are to be inserted in the order shown into an AVL tree. A, Z, B, Y, C, X, D, W, E, V, F Show how the tree appears after each insertion
2.	(a)	How is a dequeue different from stack and queue ? What are the different types of dequeue ? what are the different ways one can implement dequeue?
	(b).	Write an algorithm to implement dequeue through circular array.
3.	(a).	What is the number of nodes on the ith level of an almost birth tree with height K ?
	(b).	What are the objectives of Binary Search tree ?
	(c).	Write an algorithm to find the inorder successor of a node in a threaded Binary tree.
4.	(a).	find a minimum spanning tree of the following graph using Kruskal algorithm :
	(b).	Write Kruskal's algorithm.
5.		Discuss the difference between the following file organization techniques :     Sequential file organization    Index sequential file organization    Direct file organization Compare their storage and access efficiencies.  To what type of applications each of the techniques are suited?
6.	(a)	Write an algorithm (recursive) to implement quick-sort technique and discuss about its efficiency.
	(b)	Given an example where postorder traversal is the most appropriate way to visit a tree.  Do the same for inorder and preorder traversal.
	(c)	What is the difference between external and internal sorting ?